package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Description 快速排序
 * @Detail
 *          步骤：
 *              1、先排序一遍
 *              2、使用左递归
 *              3、使用右递归
 *          角色：
 *              1、递归
 *              2、数组指定的最小下标
 *              3、数组指定的最大下标
 *              4、左下标
 *              5、又下标
 *              6、基准值
 *                  本算法使用的基准值是数组指定最小下标对应的元素，基准值可以随便选
 *              7、临时变量
 * @Author MyPC
 * @Date 2020/7/19
 * @Version 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        int arr[]={15,2,4,8,1,5,18,6,17,22,6};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    //快速排序算法
    public static void quickSort(int[] arr,int low,int high){
        //左下标
        int start=low;
        //右下标
        int end=high;
        //基准值，取第一个为基准值
        int base=arr[low];
        while(start<end){
            //从后往前比较，获取后边较小的值，要使用arr[end] >= arr[start]，不能使用arr[end] > arr[start]
            while (start < end && arr[end] >= arr[start]){
                end--;
            }
            //如果后边较小的值小于基准值，那么交换
            if(base >= arr[end]){
                int temp=arr[end];
                arr[end]=arr[start];
                arr[start]=temp;
            }
            //从前往后比较，获取前边较大的值,要使用arr[start] <= arr[end]，不能使用arr[start] < arr[end]
            while (start < end && arr[start] <= arr[end]){
                start++;
            }
            //如果前边较大的值大于基准值，那么交换
            if(base <= arr[start]){
                int temp=arr[start];
                arr[start]=arr[end];
                arr[end]=temp;
            }
            //向左递归
            if(start>low){
                quickSort(arr,low,start-1);
            }
            //向右递归
            if(end<high){
                quickSort(arr,end+1,high);
            }
        }
    }
}
